#include<iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
    int getLen(ListNode* head) {
        int len = 0;
        while (head != NULL) {
            head = head->next;
            ++len;
        }
        return len;
    }

    ListNode* mergetSort(ListNode* head) {
        ListNode tmp(-1);
        tmp.next = head;
        int len = getLen(head);
        for (int gap = 1; gap < len; gap*=2) {
            ListNode* last = &tmp;
            while (last->next != NULL) {
                ListNode* node = last->next;
                ListNode* prev = last;
                for (int i = 0; i < gap&&node!=NULL; ++i) {
                    prev = node;
                    node = node->next;
                }
                if (node == NULL) break;
                if (prev != NULL) prev->next = NULL;
                ListNode* first = last->next, * second = node;
                for (int i = 0; i < gap && node != NULL; ++i) {
                    prev = node;
                    node = node->next;
                }
                if (prev != NULL) prev->next = NULL;
                while (first != NULL && second != NULL) {
                    if (first->val < second->val) {
                        last->next = first;
                        first = first->next;
                    }
                    else {
                        last->next = second;
                        second = second->next;
                    }
                    last = last->next;
                }
                if (first != NULL) last->next = first;
                if (second != NULL) last->next = second;
                while (last->next != NULL) last = last->next;
                last->next = node;
            }
        }
        return tmp.next;
    }
public:
    ListNode* sortList(ListNode* head) {
        return mergetSort(head);
    }
};